package 双指针.四数之和;
import java.util.*;

public class FourNum {
    public static void main(String[] args) {
        Solution so = new Solution();
        int[] arr ={1,0,-1,0,-2,2};
        List<List<Integer>> rel = so.fourSum(arr, 0);
        System.out.println(rel);
    }
}
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        //排序
        Arrays.sort(nums);
        List<List<Integer>> rel = new ArrayList<>();
        for(int i = 0;i < nums.length-3;i++){
            //去重
            if(i >= 1 && nums[i] == nums[i-1]){
                continue;
            }
            // 当前四个最小的数 > target
            if((long)nums[i]+nums[i+1]+nums[i+2]+nums[i+3] > target) break;
            // 当前最大的四个数 < target
            if((long)nums[i]+nums[nums.length-1]+nums[nums.length-2]+nums[nums.length-3] < target) continue;

            for(int j = i + 1;j < nums.length-2;j++){
                //去重
                if(j > i + 1 && nums[j] == nums[j-1]){
                    continue;
                }
                // 当前四个最小的数 > target
                if((long)nums[i]+nums[j]+nums[j+1]+nums[j+2] > target) break;
                // 当前最大的四个数 < target
                if((long)nums[i]+nums[nums.length-1]+nums[nums.length-2]+nums[j] < target) continue;

                int left = j+1,right = nums.length-1;
                long temp =(long) target - nums[i]-nums[j];
                while(left < right){
                    if(nums[left]+nums[right] > temp){
                        right--;
                    }else if(nums[left]+nums[right] < temp){
                        left++;
                    }else{
                        rel.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
                        left++;
                        right--;

                        //去重
                        while(left < right && nums[left] == nums[left-1]){
                            left++;
                        }
                        while(left < right && nums[right] == nums[right+1]){
                            right--;
                        }
                    }
                }
            }
        }
        return rel;
    }
}